QRZ! Ham Radio 4

home *** CD-ROM | disk | FTP | other *** search

/ QRZ! Ham Radio 4 / QRZ Ham Radio Callsign Database - Volume 4.iso / files / packet / misc / netconf.arc / NOCOLL.TXT < prev next >

Wrap

Text File | 1988-12-10 | 18KB | 393 lines

A High Performance, Collision-Free Packet Radio Network Phil Karn, KA9Q _A_B_S_T_R_A_C_T For the past several years, those discussing "level 3 networking" have made much of the performance gains to be had through hop-by-hop acknowledgements. In this paper I will show that, while sometimes help- ful, hop-by-hop ACKing is not the panacea it is gen- erally perceived to be. Only fundamental changes in the way we allocate and use frequencies will really fix the problem. _1. _I_n_t_r_o_d_u_c_t_i_o_n At present, our networks can best be described as "anarchistic." Single frequency digipeaters abound, and every- one knows just how likely you are to get a packet across five digipeater hops on a heavily loaded frequency [2]. Given this situation, software that provides hop-by-hop acknowledgements (e.g., NET/ROM [4]) is clearly a major win. Actively retransmitting ACKs, as in the ACK-ACK protocol [3] would yield an additional improvement. Yet NET/ROM and ACK-ACK both fail to attack the fundamental problem: _c_a_r_r_i_e_r _s_e_n_s_e _m_u_l_t_i_p_l_e _a_c_c_e_s_s (_C_S_M_A) _s_i_m_p_l_y _d_o_e_s_n'_t _w_o_r_k _v_e_r_y _w_e_l_l _o_n _a_n _o_p_e_n-_a_c_c_e_s_s _s_i_m_p_l_e_x _r_a_d_i_o _c_h_a_n_n_e_l. Two things contribute to this. The first is the well-known _h_i_d_d_e_n _t_e_r_m_i_n_a_l _p_r_o_b_l_e_m: not sensing carrier on the channel does NOT guarantee that you won't interfere with someone if you transmit. The second problem is less well known. Because it is the converse of the hidden terminal problem I will call it the _e_x_p_o_s_e_d _t_e_r_m_i_n_a_l _p_r_o_b_l_e_m.[1] A station in a good location (e.g., a mountaintop) may hear local traffic from within a distant area. Not knowing that it would not interfere with that traffic by transmitting, it defers unnecessarily and wastes an opportun- ity to reuse the frequency locally. _________________________ [1] George Flammer, WB6RAL, calls this the _w_h_i_t_e _l_i_g_h_t_n_i_n_g effect. [1] December 6, 1988 In short, the carrier detect line from the modem is often useless. There is no guarantee that you won't interfere with someone if you transmit when you don't hear a carrier, and con- versely there is no guarantee that you _w_o_u_l_d interfere with another transmission even if you transmit when you _d_o hear a carrier. It is well known (and proven in practice!) that CSMA breaks down in the presence of hidden terminals, degrading rapidly to the performance of pure Aloha (where stations transmit at will, without first monitoring the channel). With the standard Aloha assumptions (many terminals each generating a tiny fraction of the total channel load) the maximum attainable channel throughput is only 18%. This occurs at an offered load of 50%, i.e., each packet has to be transmitted about 2.7 times on the average for it to be received once. Although hop-by-hop ack- nowledgements keep these figures from getting exponentially worse across a multi-hop path, they do _n_o_t fix the fundamental problem: _C_H_A_N_N_E_L _C_O_L_L_I_S_I_O_N_S! This is a very important point. _U_s_i_n_g _l_i_n_k _l_e_v_e_l _A_C_K_s _t_o _i_m_p_r_o_v_e _p_e_r_f_o_r_m_a_n_c_e _i_s, _a_t _b_e_s_t, _a _b_a_n_d-_a_i_d _s_o_l_u_t_i_o_n. Because they represent overhead, sometimes they are actually counterpro- ductive. The real challenge, therefore, is to make collisions impossible in normal operation. I will now discuss two of the traditional methods for collision avoidance when hidden termi- nals are present. _2. _T_o_k_e_n _P_a_s_s_i_n_g One way to avoid collisions is to require each station to wait for explicit, one-at-a-time permission to transmit. When a station has sent its traffic, it passes this authority on to the next station. Since the message that grants permission to transmit is known as a _t_o_k_e_n, this scheme is known as _t_o_k_e_n _p_a_s_s_i_n_g. Token passing works well in small networks with reliable nodes and links, but it doesn't scale well. Complex recovery algorithms must be worked out to recover from lost tokens caused either by failing nodes or transmission errors. In a packet radio network with many hidden terminals, the route that the token will take must be mapped out in advance; it cannot be passed between stations that cannot communicate. This compli- cates the addition of new stations to the network. In addition, much time is wasted passing the token when there are many sta- tions in the network but only a few are actually sending traffic. Nevertheless, token passing is a completely unexplored technique in amateur radio, one that deserves serious considera- tion for special circumstances. December 6, 1988 _3. _B_u_s_y _T_o_n_e _M_u_l_t_i_p_l_e _A_c_c_e_s_s (_B_T_M_A) Another effective technique for eliminating collisions when hidden terminals are present is for each station to transmit a signal on a separate frequency whenever it is actively receiving a packet. If another node hears this _b_u_s_y _t_o_n_e, it avoids transmitting knowing that it would interfere with the reception in progress. It is not necessary for a node to couple its busy tone directly to the receiver carrier detect indication; it may drop the busy tone once it determines by examining the packet destination address that the packet is for another station. This allows _f_r_e_q_u_e_n_c_y _r_e_u_s_e (successful simultaneous use of the same frequency by two pairs of stations far enough apart not to interfere with each other). In theory, BTMA can be an effective solution to the hidden terminal problem. However, extra radio hardware is required since the busy tone transmitter must operate without interfering with data reception. In practice this means using separate fre- quency bands, and it may be difficult to get the range of the busy tone transmitter to match that of the data transmitter -- a fundamental assumption in BTMA. It is also difficult to get BTMA to solve the exposed terminal problem. Hearing a busy tone doesn't _a_l_w_a_y_s mean that you'd interfere with a receiver if its desired signal is much stronger than yours, depending on the capture ratio of the modulation method in use. Setting the busy tone's amplitude in inverse relationship to the level of the signal being received, plus lots of tricky threshold adjustments in the busy tone receivers, might make this work. _4. _C_o_n_t_e_n_t_i_o_n-_F_r_e_e _C_h_a_n_n_e_l_s The discussion so far has centered on reducing or eliminat- ing collisions when a single frequency must be shared by more than one transmitter. Contention channels are likely to be with us for some time where random end-users are involved. However, the emerging network of dedicated, "backbone" sites need not follow the same anarchistic model. The rest of this paper discusses a more disciplined approach that appears extremely attractive for such stations. One sure way to eliminate collisions is to eliminate all but one transmitter on each frequency. All other transmitters on the same frequency must be placed far enough apart so that their coverage areas do not overlap. Each station uses a separate, dedicated receiver to hear each of its neighbors; it does not listen on its own transmit frequency. A network node might look like this: Beam or Omni Beam or Omni Beam or Omni Antenna Antenna Antenna December 6, 1988 Receiver 1 Receiver 2 Receiver N ___________________________________________ | Packet switch | ___________________________________________ Transmitter Omni antenna Many things now become easier or perhaps even possible for the first time. As it is no longer necessary to "get off the frequency" quickly when a station has sent its traffic, fast transmit-receive switching is no longer required. Transmitters and power amplifiers with relays or slow-lockup synthesizers need not be modified; they could operate either continuously, or with tail timers like those in conventional voice repeaters. Similarly, coherent receiver demodulators (which work well with very low signal levels but require relatively long acquisition times) need not penalize network performance. The link receivers may be cheap pocket scanners since they need not transmit. If adjacent nodes transmit on different bands, the expense of repeater-style duplexers can be avoided, although filter cavities ("trashcans") may still be needed (especially at hilltop sites) to reject strong out-of-band signals. Since the design of this network makes collisions impossi- ble, with proper modem design and adequate RF link margins the raw packet loss rate should be very low. The occasional end- to-end retransmission of a dropped packet will be more than offset by the savings in overhead gained by avoiding link level acknowledgements. High channel speeds are much easier to handle since the packet switches are much simpler, and real time appli- cations such as packet voice become practical. Since the nodes are inherently full duplex, sliding-window transport protocols (with data packets and acknowledgements flowing simultaneously in both directions) finally make sense, as data/ack collisions are avoided. _5. _B_r_o_a_d_c_a_s_t_i_n_g In addition, some very powerful broadcast techniques become possible. Much of the traffic now handled by bulletin boards consists of undirected messages read by a wide audience. At present, our virtual circuit protocols require that a separate copy be sent to and acknowledged by every interested reader. This wastes one of the most useful and unique properties of radio: the ability of more than one receiver to hear a single transmitter. Efficient but reliable broadcasting on a very unreliable channel (e.g., an existing digipeater network) is almost impossible. However, the situation changes completely if the raw packet loss rate can be lowered to a reasonable level. December 6, 1988 Consider the operation of an ordinary voice bulletin net, one organized to disseminate information of general interest to many stations. (A good example is the Tuesday night AMSAT net on 75 meters). After the control station finishes reading, he invites requests for repeats. If conditions are good, only a few stations will respond, and the requested message fragments are retransmitted. As with the original transmission, all receiving stations are free to make use of the retransmitted information; this often preempts a second station's request for a fill. If conditions are bad, the control station may first read the entire bulletin several times (a simple form of forward error correction) to cut down the number of fill requests. _6. _F_l_o_o_d _R_o_u_t_i_n_g Given a reasonably reliable channel (i.e., one with only a single transmitter) this scheme should be easy to automate. Wide-area bulletin coverage could be achieved with a flood rout- ing scheme similar to the USENET bulletin board network. In flooding, a node originating a message transmits it to all of its neighbors. Each message contains a unique network-wide identifier (e.g., the node address concatenated with a serial number). Each receiving node maintains a list of messages it has already seen and ignores duplicates. A non-duplicate mes- sage is entered into the list and retransmitted to its neighbors until it has spread to every reachable node in the network. Flooding is extremely robust, as it tries every possible route to each node in parallel. USENET has proven this in prac- tice, despite an amazingly anarchistic network management style. It is the preferred way to reach large numbers of people, since a given message crosses each link in the network exactly once. Because of its reliability, flooding is a useful fallback for high priority point-to-point traffic when ordinary routing schemes have failed. (One often finds person-to-person messages posted on USENET because direct mail routing hasn't worked. Clearly this is to be discouraged except as a last resort because of the unnecessary load this generates.) _7. _S_u_m_m_a_r_y The use of contention-based channel access algorithms is perhaps unavoidable where end users are involved. However, such free-for-alls are inappropriate on backbone links in light of the severe performance problems involved. The evolving backbone networks should take a more enlightened approach. Instead of just attempting to patch things up at a higher layer by adding hop-by-hop acknowledgements, they should be carefully planned to avoid collisions altogether. Not only can the extra overhead of hop-by-hop acknowledgements be avoided, but qualitatively new and vastly more efficient bulletin dissemination techniques fall out almost for free. Considering the vastly improved perfor- mance and functionality that would result, the extra costs of doing so are minimal. December 6, 1988 _8. _R_e_f_e_r_e_n_c_e_s 1. Flammer, G., "Survival Training for Mountaintop Digi- peaters," 73 Magazine, August 1986 p. 68. 2. Clark, T., "The Trouble with Digipeaters," Gateway. 3. Karn, P. and Lloyd, B.: "Link Level Protocols Revisited," ARRL Amateur Radio Fifth Computer Networking Conference, pp. 5.25-5.37, Orlando, 9 March 1986. 4. Raikes, R., and Busch, M., "NET/ROM Version 1 Documenta- tion," Software 2000 Inc, May, 1987. December 6, 1988